{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1.请编写程序实现决策树算法中的选择属性进行分裂的计算过程，即实现选择使信息增益率最大的属性的过程，输入是数据集，输出是信息增益率最大的属性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.1 导包"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.2 载入数据集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset_path='../datasets/DataMining/test6/german_clean.csv'\n",
    "Xy_pd=pd.read_csv(dataset_path,header=0).fillna(0)\n",
    "Xy=Xy_pd.to_numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.3 对连续数据进行处理（基于平均值的二分法）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "Xy_2=Xy.copy()\n",
    "for i in range(Xy_2.shape[1]-1):\n",
    "    if type(Xy_2[0][i])==float:\n",
    "        Xy_2[:,i]=Xy_2[:,i]>Xy_2[:,i].mean()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.4 定义计算熵的函数\n",
    "    d1_i为字典，KV为label:对应的数量\n",
    "   count为总数,也可以在函数里计算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_entropy(d1_i,count):\n",
    "    entropy_tmp=0\n",
    "    for j in d1_i:\n",
    "        percent=d1_i[j]/count\n",
    "        entropy_tmp+=-percent*np.log2(percent)\n",
    "    return entropy_tmp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.5 计算根节点的熵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "entropy_Xy2=0\n",
    "label_clazzs={}\n",
    "for j in range(Xy_2.shape[0]): \n",
    "    label_clazz=Xy_2[j][-1]\n",
    "    if not label_clazz in label_clazzs:\n",
    "            label_clazzs[label_clazz]=0\n",
    "    label_clazzs[label_clazz]+=1\n",
    "entropy_Xy2=get_entropy(label_clazzs,Xy_2.shape[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.6 计算不同划分的 熵和固有值IV"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "entropy=[]\n",
    "IV=[]\n",
    "for i in range(Xy_2.shape[1]-1):\n",
    "    d1={}\n",
    "    count={}\n",
    "    for j in range(Xy_2.shape[0]): \n",
    "        \n",
    "        feature_clazz=Xy_2[j][i]\n",
    "        if not feature_clazz in d1:\n",
    "            d1[feature_clazz]={}\n",
    "            count[feature_clazz]=0\n",
    "        \n",
    "        label_clazz=Xy_2[j][-1]\n",
    "        if not label_clazz in d1[feature_clazz]:\n",
    "            d1[feature_clazz][label_clazz]=0\n",
    "        \n",
    "        d1[feature_clazz][label_clazz]+=1\n",
    "        count[feature_clazz]+=1\n",
    "    \n",
    "    count_percent=np.array([count[j] for j in count])/Xy_2.shape[0]\n",
    "    entropy_tmps=np.array([get_entropy(d1[j],count[j]) for j in d1])\n",
    "    entropy_tmp=(count_percent*entropy_tmps).sum()\n",
    "    entropy.append(entropy_tmp)\n",
    "    IV_template=-(count_percent*np.log(count_percent)).sum()\n",
    "    IV.append(IV_template)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.7 计算增益和增益率"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "gain=entropy_Xy2-np.array(entropy)\n",
    "gain_ratio=gain/np.array(IV)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.8 计算增益率"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "entropy_Xy =  0.8812908992306927\n",
      "entropy =  [0.7865520576780533, 0.866291049179549, 0.8376730999202525, 0.8559765463437679, 0.05750977500432694, 0.8588700294093004, 0.8531762241431075, 0.8681885766944065, 0.8773187673787509, 0.8744803494942606, 0.876493878297301, 0.8807483979872751, 0.864305713294921, 0.8357053278756971, 0.872415828923094, 0.8685377127526691, 0.87931256793018, 0.8799535423723474, 0.8803272392157833, 0.8754679082164061]\n",
      "gain =  [9.47388416e-02 1.49998501e-02 4.36177993e-02 2.53143529e-02\n",
      " 8.23781124e-01 2.24208698e-02 2.81146751e-02 1.31023225e-02\n",
      " 3.97213185e-03 6.81054974e-03 4.79702093e-03 5.42501243e-04\n",
      " 1.69851859e-02 4.55855714e-02 8.87507031e-03 1.27531865e-02\n",
      " 1.97833130e-03 1.33735686e-03 9.63660015e-04 5.82299101e-03]\n",
      "gain_ratio =  [0.07584683 0.02181737 0.03675926 0.01372598 0.12122233 0.0276301\n",
      " 0.0240327  0.00877074 0.00316791 0.00641311 0.01285255 0.00042488\n",
      " 0.0125807  0.01248011 0.01515783 0.01615344 0.00251554 0.00136507\n",
      " 0.00142849 0.03678688]\n"
     ]
    }
   ],
   "source": [
    "print(\"entropy_Xy = \",entropy_Xy2)\n",
    "print(\"entropy = \",entropy)\n",
    "print(\"gain = \",gain)\n",
    "print(\"gain_ratio = \",gain_ratio)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.9 查看最大的增益率及分类方式（发现基于下标为4的分类增益率最大，0.12122233）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "max_index= 4 ,gain_ratio= 0.121222\n"
     ]
    }
   ],
   "source": [
    "max_index=int(gain_ratio.argmax())\n",
    "print(\"max_index= {:d} ,gain_ratio= {:.6f}\".format(max_index,gain_ratio[max_index]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.调用Python自带的sklearn包里的决策树方法进行分类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1 调包"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sklearn\n",
    "from sklearn import tree\n",
    "from sklearn import preprocessing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2 将离散值转成one-hot编码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "Xdf = pd.DataFrame(Xy[:,:-1])\n",
    "# print(type(Xdf))\n",
    "onehot_indexs=[]\n",
    "not_onehot_indexs=[]\n",
    "le = preprocessing.LabelEncoder()\n",
    "for col in Xdf.columns:\n",
    "    if type(Xdf[col][0])==str:\n",
    "        f = le.fit_transform(Xdf[col])\n",
    "        Xdf[col] = f\n",
    "        onehot_indexs.append(col)\n",
    "    else :\n",
    "        not_onehot_indexs.append(col)\n",
    "\n",
    "enc = preprocessing.OneHotEncoder()\n",
    "Xdf_enc=enc.fit_transform(Xdf[onehot_indexs]).toarray()\n",
    "X_3=np.append(Xy[:,not_onehot_indexs],Xdf_enc,axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.3 训练模型并预测"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "dtc = tree.DecisionTreeClassifier(criterion=\"entropy\")\n",
    "dtc.fit(X_3,Xy[:,-1].astype('int'))\n",
    "predict=dtc.predict(X_3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.4 查看精度，为1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n"
     ]
    }
   ],
   "source": [
    "acc=np.sum(predict==Xy[:,-1])/Xy.shape[0]\n",
    "print(acc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
